package bin_tree.heap.leetcode;

import javafx.util.Pair;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 出现次数最多的前k个数
 * @author yuisama
 * @date 2022/03/03 19:15
 **/
public class Num347_TopKFreq {
    // 每个不重复的元素以及其出现的次数
    private class Freq implements Comparable<Freq> {
        private int key;
        private int times;
        public Freq(int key, int times) {
            this.key = key;
            this.times = times;
        }
        // 最小堆，元素出现的次数越多就越大
        @Override
        public int compareTo(Freq o) {
            return this.times - o.times;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        // 1.先扫描原nums数组，将每个不重复的元素以及其出现的次数存储到Map中
        Map<Integer,Integer> map = new HashMap<>();
        for (int i : nums) {
//            map.put(i,map.getOrDefault(i,0) + 1);
            if (map.containsKey(i)) {
                // 此时i已经在map中存在了
                map.put(i,map.get(i) + 1);
            }else {
                // 此时i是第一次出现
                map.put(i,1);
            }
        }
        // 2.扫描Map集合，将前k个出现频次最高的元素放入优先级队列中
        Queue<Freq> queue = new PriorityQueue<>();
        for (Map.Entry<Integer,Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            }else {
                // 判断当前堆顶元素和当前元素的出现次数关系
                Freq freq = queue.peek();
                if (entry.getValue() < freq.times) {
                    continue;
                }else {
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(), entry.getValue()));
                }
            }
        }
        // 此时优先级队列中就存储了出现次数最多的前k个pair对象
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll().key;
        }
        return ret;
    }
}